/**
 * 97. Interleaving String 交错字符串
 * https://leetcode.com/problems/interleaving-string/description/
 */

class InterleavingString {
    /**
     * 方法： 使用动态规划判断字符串s3是否可以由s1和s2交错组成
     *       dp[j]表示s1的前i个字符和s2的前j个字符是否可以交错组成s3的前i+j个字符
     *       当前字符可以来自s1或s2:
     *       - 来自s1: dp[j] = dp[j] && s1[i-1] == s3[i+j-1] 
     *       - 来自s2: dp[j] = dp[j-1] && s2[j-1] == s3[i+j-1]
     *
     * Args:
     *      s1: String - 第一个输入字符串
     *      s2: String - 第二个输入字符串  
     *      s3: String - 目标字符串
     *
     * Returns:
     *      boolean: s3是否可以由s1和s2交错组成
     *
     * Time: O(m*n) - m和n分别为s1和s2的长度，需要填充m*n的dp表
     *
     * Space: O(n) - 使用一维数组优化空间，n为s2的长度
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }

        // 使用一维数组优化空间复杂度
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 两个空字符串可以组成空字符串

        // 初始化第一行（仅使用s2的情况）
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j - 1] && (s2.charAt(j - 1) == s3.charAt(j - 1));
        }

        for (int i = 1; i <= m; i++) {
            // 初始化当前行第一个元素（仅使用s1的情况）
            dp[0] = dp[0] && (s1.charAt(i - 1) == s3.charAt(i - 1));

            for (int j = 1; j <= n; j++) {
                // 当前字符可以来自s1或s2
                boolean fromS1 = dp[j] && (s1.charAt(i - 1) == s3.charAt(i + j - 1));
                boolean fromS2 = dp[j - 1] && (s2.charAt(j - 1) == s3.charAt(i + j - 1));
                dp[j] = fromS1 || fromS2;
            }
        }

        return dp[n];
    }
}